翻訳と辞書 Words near each other ・ Yao Yanzhang ・ Yao Yao ・ Yao Ye ・ Yao Yecheng ・ Yao Yi ・ Yao Yige ・ Yao Yilin ・ Yao Youxin ・ Yao Yuanhao ・ Yao Zhe ・ Yao Zhen ・ Yao Zhenshan ・ Yao Zongxun ・ Yao'an County ・ Yao's Millionaires' Problem ・ Yao's principle ・ Yao's test ・ Yao, Chad ・ Yao, Osaka ・ Yaobei, Chaling ・ Yaochidao ・ Yaocomico ・ Yaodong ・ Yaodu District ・ Yaodu Rural Commercial Bank ・ Yaogan ・ Yaoghin ・ Yaoguai ・ Yaoguin ・ Yaogun Beijing Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Yao's principle ： ウィキペディア英語版 Yao's principle In computational complexity theory, Yao's principle or Yao's minimax principle states that the expected cost of a randomized algorithm on the worst case input, is no better than a worst-case random probability distribution of the deterministic algorithm which performs best for that distribution. Thus, to establish a lower bound on the performance of randomized algorithms, it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm can perform well against that distribution. This principle is named after Andrew Yao, who first proposed it. Yao's principle may be interpreted in game theoretic terms, via a two-player zero sum game in which one player, Alice, selects a deterministic algorithm, the other player, Bob, selects an input, and the payoff is the cost of the selected algorithm on the selected input. Any randomized algorithm ''R'' may be interpreted as a randomized choice among deterministic algorithms, and thus as a strategy for Alice. By von Neumann's minimax theorem, Bob has a randomized strategy that performs at least as well against ''R'' as it does against the best pure strategy Alice might choose; that is, Bob's strategy defines a distribution on the inputs such that the expected cost of ''R'' on that distribution (and therefore also the worst case expected cost of ''R'') is no better than the expected cost of any single deterministic algorithm against the same distribution. ==Statement== Let us state the principle for Las Vegas randomized algorithms, i.e., distributions over deterministic algorithms that are correct on every input but have varying costs. It is straightforward to adapt the principle to Monte Carlo algorithms, i.e., distributions over deterministic algorithms that have bounded costs but can be incorrect on some inputs. Consider a problem over the inputs $\backslash mathcal$, and let $\backslash mathcal$ be the set of all possible deterministic algorithms that correctly solve the problem. For any algorithm $a\; \backslash in\; \backslash mathcal$ and input $x\; \backslash in\; \backslash mathcal$, let $c(a,\; x)\; \backslash geq\; 0$ be the cost of algorithm $a$ run on input $x$. Let $p$ be a probability distributions over the algorithms $\backslash mathcal$, and let $A$ denote a random algorithm chosen according to $p$. Let $q$ be a probability distribution over the inputs $\backslash mathcal$, and let $X$ denote a random input chosen according to $q$. Then, : $\backslash underset\backslash \; \backslash bold()\; \backslash geq\; \backslash underset\backslash \; \backslash bold()$ , i.e., the worst-case expected cost of the randomized algorithm is at least the cost of the best deterministic algorithm against input distribution $q$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Yao's principle」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.